package io.github.hadyang.leetcode.bytedance;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 合并K个排序链表 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 *
 * <p>示例:
 *
 * <p>输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
 *
 * @author haoyang.shi
 */
public class Link1025 {
  public ListNode mergeKLists1(ListNode[] lists) {
    if (lists.length == 0) {
      return null;
    }

    if (lists.length == 1) {
      return lists[0];
    }

    ListNode head = new ListNode(-1);
    ListNode cursor = head;

    while (true) {
      int minListIndex = -1;
      for (int i = 0; i < lists.length; i++) {
        ListNode cur = lists[i];

        if (cur == null) {
          continue;
        }

        if (minListIndex == -1) {
          minListIndex = i;
        }

        if (cur.val < lists[minListIndex].val) {
          minListIndex = i;
        }
      }

      if (minListIndex == -1) {
        break;
      }

      ListNode min = lists[minListIndex];
      if (min == null) {
        break;
      }

      lists[minListIndex] = min.next;
      cursor.next = min;
      cursor = cursor.next;
    }

    return head.next;
  }

  public ListNode mergeKLists2(ListNode[] lists) {
    if (lists.length == 0) {
      return null;
    }

    if (lists.length == 1) {
      return lists[0];
    }

    List<ListNode> nodes = new ArrayList<>();
    for (ListNode node : lists) {
      if (node == null) {
        continue;
      }

      nodes.add(node);
    }

    if (nodes.isEmpty()) {
      return null;
    }

    if (nodes.size() == 1) {
      return nodes.get(0);
    }

    ListNode res = nodes.get(0);
    for (int i = 1; i < nodes.size(); i++) {
      res = mergeTwoList(res, nodes.get(i));
    }
    return res;
  }

  private ListNode mergeTwoList(ListNode l1, ListNode l2) {
    if (l1 == null && l2 == null) {
      return null;
    }

    if (l1 == null) {
      return l2;
    }

    if (l2 == null) {
      return l1;
    }

    ListNode head;

    if (l1.val > l2.val) {
      head = l2;
      l2 = l2.next;
    } else {
      head = l1;
      l1 = l1.next;
    }

    ListNode res = head;
    while (true) {
      ListNode cur;
      if (l1 == null && l2 == null) {
        break;
      }

      if (l1 == null) {
        cur = l2;
        l2 = l2.next;
      } else if (l2 == null) {
        cur = l1;
        l1 = l1.next;
      } else if (l1.val > l2.val) {
        cur = l2;
        l2 = l2.next;
      } else {
        cur = l1;
        l1 = l1.next;
      }

      head.next = cur;
      head = head.next;
    }

    return res;
  }

  public ListNode mergeKLists3(ListNode[] lists) {
    if (lists == null) {
      return null;
    }

    Queue<ListNode> set = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

    for (ListNode node : lists) {
      while (node != null) {
        set.add(node);
        node = node.next;
      }
    }

    ListNode head = new ListNode(-1);
    ListNode res = head;
    ListNode cur;
    while ((cur = set.poll()) != null) {
      head.next = cur;
      head = head.next;
    }

    head.next = null;
    return res.next;
  }

  private static class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }

    @Override
    public String toString() {
      return "ListNode{" + "val=" + val + '}';
    }
  }

  public static void main(String[] args) {
    ListNode head1 = new ListNode(-2);
    ListNode head2 = new ListNode(-1);
    ListNode head3 = new ListNode(-1);
    head1.next = head2;
    head2.next = head3;

    ListNode head4 = new ListNode(1);
    ListNode head5 = new ListNode(3);
    ListNode head6 = new ListNode(4);
    head4.next = head5;
    head5.next = head6;

    ListNode head7 = new ListNode(2);
    ListNode head8 = new ListNode(6);
    head7.next = head8;

    Link1025 main = new Link1025();

    ListNode res = main.mergeKLists1(new ListNode[] {head1, head4, head7});

    while (res != null) {
      System.out.print(res.val);
      res = res.next;
    }
  }
}
